/**
 * 
 */
package utils;
import java.util.*;

import operators.*;
import operators.Attribute.type_map;
/**
 * @author zengzh
 *
 */
public class GenERD {
	
	/********************************  Fonda *********************************
	 * class RELATION represents inputs
	 * class ENTITY is results of identifying core relation
	 * class RELATIONSHIP is results of identifying inter-object relationships
	 *************************************************************************/
	public Vector<Relation> rel_list;
	public Vector<Entity> elist;
	//public Vector<Relationship> rlist;
	
	
	/************************************ Fonda ******************************/
	public Vector<Isa> isalist;
	public Vector<Relationship> rshlist;
	
	public GenERD(Vector<Relation> rel_list) {
		
		this.rel_list = rel_list;
		this.elist = new Vector<Entity>();
		//this.rlist = new Vector<Relationship>();
		
		/********************************************************************/
		this.isalist = new Vector<Isa>();
		this.rshlist = new Vector<Relationship>();
	}
	
	public GenERD(String schema_str, String keys_str, String ind_str)
	{
		this.rel_list = this.ParseStr(schema_str, keys_str, ind_str);
		this.elist = new Vector<Entity>();
		//this.rlist = new Vector<Relationship>();
		this.isalist = new Vector<Isa>();
		this.rshlist = new Vector<Relationship>();
	}
	
	public String rmnoisechar(String str)
	{
		String result = str;
		while(true)
		{
			int idx = result.indexOf('\n');
			if(idx == -1)
			{
				idx = result.indexOf(' ');
				if(idx == -1)
				{
					return result;
				}
			}
			result = result.substring(0,idx)+result.substring(idx+1);
		}
	}
	
	public Vector<Relation> ParseStr(String schema_str, String keys_str, String ind_str)
	{
		schema_str = rmnoisechar(schema_str);
		keys_str = rmnoisechar(keys_str);
		ind_str = rmnoisechar(ind_str);
		Vector<Relation> rel_list = new Vector<Relation>();
		
		System.out.println("===> parse the user input");
		
		StringTokenizer reltoken = new StringTokenizer(schema_str, ";");
		while(reltoken.hasMoreTokens())
		{
			String rel = reltoken.nextToken();
			String relname = rel.substring(0, rel.indexOf('('));
			String attrs = rel.substring(rel.indexOf('(')+1, rel.indexOf(')'));
			Relation r = new Relation(relname);
			StringTokenizer attrtoken = new StringTokenizer(attrs, ",");
			while(attrtoken.hasMoreTokens())
			{
				String attr = attrtoken.nextToken();
				r.addAttr(attr);
			}
			rel_list.add(r);
		}
		
		StringTokenizer keystoken = new StringTokenizer(keys_str, ";");
		while(keystoken.hasMoreTokens())
		{
			String keys = keystoken.nextToken();
			String relname = keys.substring(0, keys.indexOf(':'));
			Relation r = null;
			for(int i = 0; i < rel_list.size(); i++)
			{
				if(rel_list.elementAt(i).Relname.equals(relname))
				{
					r = rel_list.elementAt(i);
					break;
				}
			}
			String keylist = keys.substring(keys.indexOf('{'));
			StringTokenizer keytoken = new StringTokenizer(keylist, "}");
			while(keytoken.hasMoreTokens())
			{
				String rawkey = (keytoken.nextToken()).substring(1);
				Vector<String> key = new Vector<String>();
				StringTokenizer keyetoken = new StringTokenizer(rawkey, ",");
				while(keyetoken.hasMoreTokens())
				{
					String keyelement = keyetoken.nextToken();
					key.add(keyelement);
				}
				r.addKey(key);
			}
		}
		
		StringTokenizer indstoken = new StringTokenizer(ind_str, ";");
		while(indstoken.hasMoreTokens())
		{
			String ind = indstoken.nextToken();
			String indlhs = ind.substring(0,ind.indexOf('*'));
			String indrhs = ind.substring(ind.indexOf('*')+1);
			String lhs_rel = indlhs.substring(0, indlhs.indexOf('['));
			String lhs_attrs = indlhs.substring(indlhs.indexOf('[')+1 ,indlhs.indexOf(']'));
			String rhs_rel = indrhs.substring(0, indrhs.indexOf('['));
			String rhs_attrs = indrhs.substring(indrhs.indexOf('[')+1, indrhs.indexOf(']'));
			
			Relation r = null;
			for(int i = 0; i < rel_list.size(); i++)
			{
				if(rel_list.elementAt(i).Relname.equals(lhs_rel))
				{
					r = rel_list.elementAt(i);
					break;
				}
			}
			StringTokenizer lhs_attrstoken = new StringTokenizer(lhs_attrs, ",");
			Vector<String> lhs_attrlist = new Vector<String>();
			while(lhs_attrstoken.hasMoreTokens())
			{
				String lhs_attr = lhs_attrstoken.nextToken();
				lhs_attrlist.add(lhs_attr);
			}
			StringTokenizer rhs_attrstoken = new StringTokenizer(rhs_attrs, ",");
			
			Vector<String> rhs_attrlist = new Vector<String>();
			while(rhs_attrstoken.hasMoreTokens())
			{
				String rhs_attr = rhs_attrstoken.nextToken();
				rhs_attrlist.add(rhs_attr);
			}
			Pair<String, Vector<String>> IDpair =  new Pair<String, Vector<String>>(rhs_rel, rhs_attrlist);
			r.addInd(new Pair<Vector<String>,Pair<String,Vector<String>>>(lhs_attrlist, IDpair));
		}
		
		return rel_list;
	}
	
	public void PrintEntity()
	{
		
		for(int i = 0; i < this.elist.size(); i++)
		{
			Entity en = this.elist.elementAt(i);
			if(en instanceof WeakEntity)
			{
				System.out.println("Entity: " + en.entity_name + " IDEntity: " + ((WeakEntity)en).IDEntity.entity_name);
				System.out.print("GlobalKeys: ");
				for(int j = 0; j < ((WeakEntity)en).getGlobalpkey().size(); j++)
				{
					System.out.print(((WeakEntity)en).getGlobalpkey().elementAt(j));
				}
				System.out.print("\nLocalKeys: ");
				for(int j = 0; j < ((WeakEntity)en).getLocalkeys().size(); j++)
				{
					Vector<String> localkey = ((WeakEntity)en).getLocalkeys().elementAt(j);
					for(int k = 0; k < localkey.size(); k++)
					{
						System.out.print(localkey.elementAt(k)+" ");
					}
				}
				System.out.print("\n");
			}
			else
			{
				System.out.println("Entity: " + en.entity_name);
			}
			for(int j = 0; j < en.attr_list.size(); j++)
			{
				Attribute attr = en.attr_list.elementAt(j);
				System.out.println("Attribute: " + attr.attrname + " Type: " + attr.attr_type);
			}
		}
	}
	
	public void PrintRelationship()
	{
		
		for(int i = 0; i < this.isalist.size(); i++)
		{
			Entity suben = this.elist.elementAt(this.isalist.elementAt(i).ls);
			Entity en = this.elist.elementAt(this.isalist.elementAt(i).rs);
			System.out.println("ISA Hierarchy:"+ suben.entity_name + " ISA " + en.entity_name);
		}
		for(int j = 0; j < this.rshlist.size(); j++)
		{
			if(this.rshlist.elementAt(j).car == 3)
			{
				continue;
			}
			Relationship rsh = this.rshlist.elementAt(j);
			
			System.out.println("Relationship: " + rsh.name);
			System.out.print("involved entities: ");
			for(int k = 0; k < rsh.entityIndex.size(); k++)
			{
				System.out.print(this.elist.elementAt(Integer.parseInt(rsh.entityIndex.elementAt(k))).entity_name+" ");
			}
			System.out.print(" Cadinality: ");
			for(int k = 0; k < rsh.cardinality.size(); k++)
			{
				System.out.print(rsh.cardinality.elementAt(k)+":");
			}
			System.out.println("");
			for(int m = 0; m < rsh.attrlist.size(); m++)
			{
				Attribute attr = rsh.attrlist.elementAt(m);
				System.out.println("Attribute: " + attr.attrname + " Type: " + attr.attr_type);
			}
		}
	}
	
	public void GenEntity() {

		for (int i = 0; i < this.rel_list.size(); i++) {
			Relation r = this.rel_list.elementAt(i);
			/*
			 * core relation case 1
			 */
			if (!chkInD(r, false) && r.ind_list.size() == 0) {
				Entity newEn = new Entity(r.Relname);
				for (int j = 0; j < r.keys.size(); j++) {
					newEn.addKeys(r.keys.elementAt(j));
				}
				for (int k = 0; k < r.attr_list.size(); k++) {
					if (chkkeys(r.attr_list.elementAt(k), newEn.keys)) {
						Attribute a = new Attribute(r.attr_list.elementAt(k),
								type_map.one2one);
						newEn.addAttr(a);
					} else {
						Attribute a = new Attribute(r.attr_list.elementAt(k));
						newEn.addAttr(a);
					}
				}
				this.elist.add(newEn);
			}
			/*
			 * core relation case 2
			 */
			else if (chkInD(r, false) && countForkey(r, false) < 2) {
				if (!chkInD(r, true)) {
					Entity newEn = new Entity(r.Relname);
					for (int j = 0; j < r.keys.size(); j++) {
						newEn.addKeys(r.keys.elementAt(j));
					}
					for (int k = 0; k < r.attr_list.size(); k++) {
						if(chkattr(r.attr_list.elementAt(k), r)&& !chkkeys(r.attr_list.elementAt(k),r.keys))
						{
							continue;
						}
						if (chkkeys(r.attr_list.elementAt(k), newEn.keys)) {
							Attribute a = new Attribute(
									r.attr_list.elementAt(k), type_map.one2one);
							newEn.addAttr(a);
						} else {
							Attribute a = new Attribute(
									r.attr_list.elementAt(k));
							newEn.addAttr(a);
						}
					}
					this.elist.add(newEn);
				}
			}
		}
	}

	public void GenWEntity() {
		/*
		 * core relation case 3. Generate weak entity
		 */
		for (int i = 0; i < this.rel_list.size(); i++) {
			Relation r = this.rel_list.elementAt(i);
			Relation r0 = null;
			for (int j = 0; j < this.elist.size(); j++) {
				boolean foundWE = false;
				for (int k = 0; k < this.rel_list.size(); k++) {
					if (this.rel_list.elementAt(k).Relname.equals(this.elist
							.elementAt(j).entity_name)) {
						r0 = this.rel_list.elementAt(k);
						break;
					}
				}
				if(r0 != null)
				{
					if(r.keys.elementAt(0).size() > r0.keys.elementAt(0).size() && 
							r.keys.elementAt(0).containsAll(r0.keys.elementAt(0)))
					{
						for(int m = 0; m < r.ind_list.size(); m++)
						{
							if(r.ind_list.elementAt(m).head.size() == r0.keys.elementAt(0).size()
									&& r0.keys.elementAt(0).containsAll(r.ind_list.elementAt(m).head)
									&& r.ind_list.elementAt(m).tail.head.equals(r0.Relname))
							{
								if(countForkey(r, true) < 2 
									&& (chkInD(r, false) || (r.attr_list.size()-countPriattr(r)) > 0))
								{
									foundWE = true;
									WeakEntity newWE = new WeakEntity(r.Relname, this.elist.elementAt(j));

									for (int n = 0; n < r.keys.size(); n++) {
										newWE.addKeys(r.keys.elementAt(n));
									}
									for (int l = 0; l < r.attr_list.size(); l++) {
										if(r0.keys.elementAt(0).contains(r.attr_list.elementAt(l))
												|| (chkattr(r.attr_list.elementAt(l), r) && !chkkeys(r.attr_list.elementAt(l),r.keys)))
										{
											continue;
										}
										Attribute a = new Attribute(r.attr_list.elementAt(l));
										newWE.addAttr(a);
									}
									this.elist.add(newWE);
									
									Relationship ID = new Relationship("ID",3);
									Vector<String> entityIdx = new Vector<String>();
									entityIdx.add(Integer.toString(j));
									entityIdx.add(Integer.toString(this.elist.indexOf(newWE)));
									ID.addEntityIndex(entityIdx);
									this.rshlist.add(ID);
									
									break;
								}
							}
						}
					}
				}
				if(foundWE)
					break;
			}
		}
	}
	
	public void GenMulAttr()
	{
		/*
		 * component relation. played as multi-valued attributes
		 */
		for(int i = 0; i < this.elist.size(); i++)
		{
			Relation r = null;
			for (int j = 0; j < this.rel_list.size(); j++) {
				if (this.rel_list.elementAt(j).Relname.equals(this.elist
						.elementAt(i).entity_name)) {
					r = this.rel_list.elementAt(j);
					break;
				}
			}
			if(r != null)
			{
				for(int k = 0; k < this.rel_list.size(); k++)
				{
					Relation r1 = this.rel_list.elementAt(k);
					for(int m = 0; m < r1.ind_list.size(); m++)
					{
						if(r1.ind_list.elementAt(m).tail.head.equals(r.Relname))
						{
							for(int l = 0; l < r.keys.size(); l++)
							{
								if(r.keys.elementAt(l).size() == r1.ind_list.elementAt(m).tail.tail.size()
										&& r1.ind_list.elementAt(m).tail.tail.containsAll(r.keys.elementAt(l))
										&& !chkInD(r1, false) && countForkey(r1, false) < 2
										&& r1.attr_list.size() == r.keys.elementAt(l).size()+1)
								{
									int forkeytype = chkattrs(r1.ind_list.elementAt(m).head, r1);
									if(forkeytype == 0)
									{
										for(int n = 0; n < r1.attr_list.size(); n++)
										{
											if(r1.ind_list.elementAt(m).head.contains(r1.attr_list.elementAt(n)))
											{
												continue;
											}
											Attribute a = new Attribute(r1.attr_list.elementAt(n));
											this.elist.elementAt(i).addAttr(a);
										}
									}
									if(forkeytype == 1)
									{
										for(int n = 0; n < r1.attr_list.size(); n++)
										{
											if(r1.ind_list.elementAt(m).head.contains(r1.attr_list.elementAt(n)))
											{
												continue;
											}
											Attribute a = new Attribute(r1.attr_list.elementAt(n),type_map.many2many);
											this.elist.elementAt(i).addAttr(a);
										}
									}
									if(forkeytype == 2)
									{
										for(int n = 0; n < r1.attr_list.size(); n++)
										{
											if(r1.ind_list.elementAt(m).head.contains(r1.attr_list.elementAt(n)))
											{
												continue;
											}
											Attribute a = new Attribute(r1.attr_list.elementAt(n),type_map.one2many);
											this.elist.elementAt(i).addAttr(a);
										}
									}
								}
							}				
						}
					}
				}
			}
		}
	}

	public int countPriattr(Relation r)
	{
		int count = 0;
		for(int i = 0; i< r.attr_list.size(); i++)
		{
			for(int j = 0; j < r.keys.size(); j++)
			{
				if(r.keys.elementAt(j).contains(r.attr_list.elementAt(i)))
				{
					count++;
					break;
				}
			}
		}
		return count;
	}
	
	public int countForkey(Relation r, boolean chkprikey)
	{
		int count = 0;
		for(int i = 0; i < r.ind_list.size(); i++)
		{
			String relname = r.ind_list.elementAt(i).tail.head;
			Vector<String> attrlist = r.ind_list.elementAt(i).tail.tail;
			Relation r0 = null;
			if(chkprikey && !r.keys.elementAt(0).containsAll(r.ind_list.elementAt(i).head))
			{
				continue;
			}
			for(int j = 0; j < this.rel_list.size(); j++)
			{
				if(this.rel_list.elementAt(j).Relname.equals(relname))
				{
					r0 = this.rel_list.elementAt(j);
					break;
				}
			}
			if(r0 != null)
			{
				for(int k = 0; k < r0.keys.size(); k++)
				{
					if(r0.keys.elementAt(k).size() == attrlist.size() && attrlist.containsAll(r0.keys.elementAt(k)))
					{
						count++;
						break;
					}
				}
			}
			
		}
		return count;
	}

	public boolean chkInD(Relation r, boolean chkset) {
		for (int i = 0; i < this.rel_list.size(); i++) {
			Relation r1 = this.rel_list.elementAt(i);
			for (int j = 0; j < r1.ind_list.size(); j++) {
				if (!chkset && r1.ind_list.elementAt(j).tail.head.equals(r.Relname)) {
					for(int k = 0; k < r.keys.size(); k++)
					{
						if(r.keys.elementAt(k).size() == r1.ind_list.elementAt(j).tail.tail.size()
								&& r1.ind_list.elementAt(j).tail.tail.containsAll(r.keys.elementAt(k)))
						{
							return true;
						}
					}
				}
				if (chkset) {
					Pair<Vector<String>, Pair<String, Vector<String>>> ind = r1.ind_list
							.elementAt(j);
					if (r.keys.elementAt(0).size() > ind.tail.tail.size()
							&& r.keys.elementAt(0).containsAll(ind.tail.tail)) {
						return true;
					}
				}
			}
		}
		return false;
	}

	public int chkattrs(Vector<String> attrs, Relation r)
	{
		/*
		 * return 0 candidate key, 1 part of key, 2 non prime attributes, -1 others.
		 */
		boolean overlap = false;
		for(int i = 0; i < r.keys.size(); i++)
		{
			if(r.keys.elementAt(i).size() > attrs.size() && r.keys.elementAt(i).containsAll(attrs))
			{
				return 1;
			}
			if(r.keys.elementAt(i).size() == attrs.size() && r.keys.elementAt(i).containsAll(attrs))
			{
				return 0;
			}
			for(int j = 0; j < attrs.size(); j++)
			{
				if(r.keys.elementAt(i).contains(attrs.elementAt(j)))
				{
					overlap = true;
					return -1;
				}
					
			}
		}
		if(!overlap)
		{
			return 2;
		}
		else
		{
			return -1;
		}
	}
	
	public boolean chkattr(String attr, Relation r)
	{
		for(int i = 0; i < r.ind_list.size(); i++)
		{
			if(r.ind_list.elementAt(i).head.contains(attr))
			{
				return true;
			}
		}
		return false;
	}
	
	public boolean chkkeys(String relattr, Vector<Vector<String>> entitykeys) {
		for (int i = 0; i < entitykeys.size(); i++) {
			if (entitykeys.elementAt(i).size() == 1
					&& entitykeys.elementAt(i).elementAt(0).equals(relattr)) {
				return true;
			}
		}
		return false;
	}

	// identify ISA hierarchy
	public void ISA()
	{
		int i,j;
		int entityNo;
		int isa_L, isa_R;
		
		for(i = 0; i < rel_list.size(); i++){
			entityNo = isCore(rel_list.elementAt(i).Relname);
			// this relation is a core relation
			// then check if any inclusion dependency's left side is key
			if(entityNo >= 0){
				isa_L = entityNo;
				// any inclusion dependency
				for(j = 0; j < rel_list.elementAt(i).ind_list.size(); j++){
					// left side is key
					Vector<String> ls = rel_list.elementAt(i).ind_list.elementAt(j).head;
					if(isKey(entityNo, ls)){
						// check righ side's relation is a core relation
						entityNo = isCore(rel_list.elementAt(i).ind_list.elementAt(j).tail.head);
						if(entityNo >= 0){
							isa_R = entityNo;
							Vector<String> rs = rel_list.elementAt(i).ind_list.elementAt(j).tail.tail;
							if(isKey(entityNo, rs)){
								Isa obj = new Isa(isa_L, isa_R);
								isalist.add(obj);
							}// end if -> add an ISA hierarchy
						}// end if right side is a core relation
					}// end if left side is key
				}// end for any inclusion dependency
			}// end if relation is a core relation	
		}
		//after finding out ISA hierarchy, check R1 ISA R2 and R2 ISA R1
		combineISA();
		
	}
	// identify relationships
	public void relationship(){
		
		// 3 forms
		// 1. primary keys =  disjoint foreign keys
		// 2. one+ foreign key
		// 3. all keys with one+ foreign key and one+ attribute
		int i;
		// No.1 form 
		for(i = 0; i < rel_list.size(); i++){
			// at least two FKs
			for(int j = 0; j < rel_list.elementAt(i).keys.size(); j++){
				Vector<String> vs = findFKs(rel_list.elementAt(i).keys.elementAt(j));					
				int result = refineFKs(vs, i, j);
				if((oneNonFK(vs)==false)&&allFKs(vs)&&(onePlusFKs(vs)==true||result>1)){	
					Relationship rsh = new Relationship(rel_list.elementAt(i).Relname, Relationship.M2M);
					rsh.addKeys(rel_list.elementAt(i).keys);
					rsh.addEntityIndex(vs);
					rsh.addAttr(rel_list.elementAt(i).attr_list);
					rshlist.add(rsh);
				}
			}
		}// end for rel_list
		// No.2 form
		for(i = 0; i < rel_list.size(); i++){
				for(int j = 0; j < rel_list.elementAt(i).keys.size(); j++){
					Vector<String> vs = findFKs(rel_list.elementAt(i).keys.elementAt(j));
					refineFKs(vs, i, j);
					Vector<String> vs_att = findFKs(rel_list.elementAt(i).attr_list);
					int result = refineFKs(vs_att,i,j);
					if((onePlusFKs(vs_att)==true)||(result>1))
						if(oneNonFK(vs_att)&&attFK(vs,vs_att)){
							Relationship rsh = new Relationship("R"+rel_list.elementAt(i).Relname,Relationship.M21);
							rsh.addKeys(rel_list.elementAt(i).keys);
							prune(rel_list.elementAt(i).attr_list, vs, vs_att);
							rsh.addEntityIndex(vs,vs_att);
							rsh.addAttr(rel_list.elementAt(i).attr_list);
							rshlist.add(rsh);
						}
				}
		}
		// No.3 form
		for(i = 0; i < rel_list.size(); i++){
			// all keys
			if(rel_list.elementAt(i).keys.size() == 1)
				if(rel_list.elementAt(i).attr_list.size() == rel_list.elementAt(i).keys.elementAt(0).size()){
					Vector <String> vs = findFKs(rel_list.elementAt(i).keys.elementAt(0));
					int result = refineFKs(vs,i,0);
					if(((onePlusFKs(vs)==true)||(result>1))&&oneNonFK(vs)){
						int pos = belongTo(vs,rshlist);
						if(pos > -1){	
							rshlist.elementAt(pos).addAttr(vs,rel_list.elementAt(i).attr_list);
						}
						else{
							Relationship rsh = new Relationship(rel_list.elementAt(i).Relname, Relationship.M2M);
							rsh.addKeys(rel_list.elementAt(i).keys);
							rsh.addEntityIndex(vs);
							rsh.addAttr(rel_list.elementAt(i).attr_list);
							rshlist.add(rsh);
						}
					}
				}
			}

		System.out.print("");
		
		
	}

	private void prune(Vector<String> attr_list, Vector<String> vs, Vector<String> vs_att) {
		
		int i,j,k;
		for(i = 0; i < vs_att.size(); i++){
			if(Integer.parseInt(vs_att.elementAt(i))<0)
				for(j = 0; j < vs.size(); j++){
					for(k = 0; k < elist.elementAt(Integer.parseInt(vs.elementAt(j))).attr_list.size();k++)
					if(attr_list.elementAt(i).equals(elist.elementAt(Integer.parseInt(vs.elementAt(j))).attr_list.elementAt(k).attrname))
						vs_att.set(i, "-2");
				}
		}
	
	}

	private int belongTo(Vector<String> vs, Vector<Relationship> rshlist) {
		
		Vector<String> vsFK = new Vector<String>();
		int i,j,k;
		
		for(i = 0; i < vs.size(); i++) 
			if(!vs.elementAt(i).equals("-1"))
				vsFK.add(vs.elementAt(i));
		for(i = 0; i < vsFK.size(); i++)
			for(j = i+1; j < vsFK.size(); j++)
				if(vsFK.elementAt(i).equals(vsFK.elementAt(j)))
					vsFK.remove(j);
		
		for(i = 0; i < rshlist.size(); i++){
			
			Vector<String> vsFKcpy = new Vector<String>(vsFK.size());
			for(k = 0; k < vsFK.size(); k++)
				vsFKcpy.add(vsFK.elementAt(k));
			
			for(j = 0; j < rshlist.elementAt(i).entityIndex.size(); j++){
				for(k = 0; k < vsFKcpy.size(); k++)
					if(rshlist.elementAt(i).entityIndex.elementAt(j).equals(vsFKcpy.elementAt(k)))
						vsFKcpy.remove(k);
			}
			
			if(vsFKcpy.size()<1)
				return i;
		}
		
		return -1;
	}

	private boolean attFK(Vector<String> vs, Vector<String> vs_att) {
		
		Vector<String> cpy = new Vector<String>();
		for(int i = 0; i <vs_att.size(); i++)
			cpy.add(vs_att.elementAt(i));
		
		for(int i = 0; i < vs.size(); i++){
			for(int j = 0; j < cpy.size(); j++){
				if(vs.elementAt(i).equals(cpy.elementAt(j)))
					cpy.remove(j);
			}
		}
		
		int count = 0;
		for(int i = 0; i < cpy.size(); i++)
			if(Integer.parseInt(cpy.elementAt(i))>-1)
				count++;
		if(count>0)
			return true;
		return false;
	}

	private int refineFKs(Vector<String> vs, int relPos, int keyPos) {
		
		Vector<String> rKey = new Vector<String>();
		rKey = rel_list.elementAt(relPos).keys.elementAt(keyPos);
		int result = 0;
		
		int i;
		for(i = 0; i < rel_list.elementAt(relPos).ind_list.size(); i++){
			// whichEntity > 0 indicates referencing a entity
			int whichEntity = isPK(rel_list.elementAt(relPos).ind_list.elementAt(i).tail.head,
						rel_list.elementAt(relPos).ind_list.elementAt(i).tail.tail);
			if(whichEntity > 0){
				for(int j = 0; j < rel_list.elementAt(relPos).ind_list.elementAt(i).head.size(); j++){
					int x = getPos(rel_list.elementAt(relPos).ind_list.elementAt(i).head.elementAt(j),rKey);
						if(x >= 0)
							if(vs.elementAt(x).equals("-1"))
								vs.set(x, Integer.toString(whichEntity));			
				}
				result++;
			}
		}
		return result;
	}

	private int isPK(String ename, Vector<String> key) {
		
		int pos = -1; //whichenrity
		boolean flag = false;
		
		for(int i = 0; i < elist.size(); i++){
			
			if(elist.elementAt(i).entity_name.equals(ename)){
				
				pos = i;
				
				for(int j = 0; j < elist.elementAt(i).keys.size(); j++){
					
					if(key.size()==elist.elementAt(i).keys.elementAt(j).size())
						flag = true;
					
					for(int k = 0; k < elist.elementAt(i).keys.elementAt(j).size(); k++){
						if(!key.elementAt(k).equals(elist.elementAt(i).keys.elementAt(j).elementAt(k))){
							flag = false;
							break;
						}
					}
					
					if(flag == true)
						return pos;
				}
			}
		}
		
		return pos;
	}

	private boolean oneNonFK(Vector<String> vs) {
		int count = 0;
		for(int i = 0; i < vs.size(); i++)
			if(vs.elementAt(i).equals("-1"))
				count++;
		if(count>0)
			return true;
		else
			return false;
	}

	private boolean onePlusFKs(Vector<String> vs) {
		
		String s = new String();
		int i;
		
		for (i = 0; i < vs.size(); i++){
			if(vs.elementAt(i).equals("-1") == false){
				//test.add(Integer.toString(i));
				s = vs.elementAt(i);
				break;
			}
		}
		
		for(int j = i+1; j < vs.size(); j++){
			if(!s.equals(vs.elementAt(j))&&!vs.elementAt(j).equals("-1"))
				return true;
		}
				
		return false;
	}
	
	private int getPos(String s, Vector<String> rKey) {
		
		int pos = -1;
		
		for(int i = 0; i < rKey.size(); i++)
			if(rKey.elementAt(i).equals(s))
				return i;
		
		return pos;
	}

	private boolean allFKs(Vector<String> vs){
		for(int i = 0; i < vs.size(); i++)
			if(vs.elementAt(i).equals("-1"))
				return false;
		return true;
	}
	
	private Vector<String> findFKs(Vector<String> keys) {
		
		// entityIndex is integer converted to string
		Vector<String> entityIndex = new Vector<String>(keys.size());
		String s = new String(Integer.toString(-1));
		int i;
		for(i = 0; i < keys.size(); i++) // initialized to be not FK
			entityIndex.add(s);
		
		for(i = 0; i < elist.size(); i++)
			if(elist.elementAt(i) instanceof Entity)
				isFK(keys, entityIndex, i);
		
		for(i = 0; i < elist.size(); i++)
			if(elist.elementAt(i) instanceof WeakEntity)
				isFK(keys, entityIndex, i);
		
		return entityIndex;
		
	}
	private void isFK(Vector<String> relationKeys, Vector<String> index, int entityPos) {
		
		int i, j, k;
		
		for(i = 0; i < elist.elementAt(entityPos).keys.size(); i++){
			
			Vector<String> oneKey = elist.elementAt(entityPos).keys.elementAt(i);
			Vector<String> pos = new Vector<String>();
	
			boolean found = false;
			
			for(j = 0; j < oneKey.size(); j++){
				
				found = false;
				
				for(k = 0; k < relationKeys.size(); k++){
					if(oneKey.elementAt(j).equals(relationKeys.elementAt(k))){
						found = true;
						pos.add(Integer.toString(k));
					}
				}
				
				if(!found){
					break;
				}
			}
			
			if(found)
				for(k = 0; k < pos.size(); k++)
					index.set(Integer.parseInt(pos.elementAt(k)), Integer.toString(entityPos));
		}
	}
	private void combineISA() {
		for(int i = 0; i < isalist.size(); i++){
			int left = isalist.elementAt(i).ls;
			int right = isalist.elementAt(i).rs;
			for(int j = i+1; j < isalist.size(); j++){
				if(isalist.elementAt(j).rs == left)
					if(isalist.elementAt(j).ls == right)
						isalist.remove(j);
			}
		}
	}

	// check left side is a key
	private boolean isKey(int pos, Vector<String> ls) {
		for(int i = 0; i < elist.elementAt(pos).keys.size(); i++){
			Vector<String> s = elist.elementAt(pos).keys.elementAt(i);
			if(equal(ls, s))
				return true;
		}
		return false;
	}

	// check two vector have the same content
	private boolean equal(Vector<String> ls, Vector<String> s) {
		if(ls.size() == s.size()){
			for(int i=0; i < ls.size(); i++){
				if(ls.elementAt(i).equals(s.elementAt(i)) == false)
					return false;
			}
			return true;
		}
		return false;
	}
	// check if a core relation
	private int isCore(String relname) {
		
		int result = -1;
		int i;
		for(i = 0; i < elist.size(); i++)
			if(relname.equals(elist.elementAt(i).entity_name))
				return i;
		return result;
	}

	public void printISA() {
		System.err.println("printISA "+isalist.size());
		System.err.println(elist.elementAt(isalist.elementAt(0).ls).entity_name+" ISA "+elist.elementAt(isalist.elementAt(0).rs).entity_name+" with "+isalist.elementAt(0).type);
	}

}
